#include <iostream>
#include <string>
using namespace std;

/**
 * @方法: dp
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
bool dp[1002][1002];
string longestPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int i = 0; i < n - 1; i++)
        if (s[i] == s[i + 1]) dp[i][i + 1] = 1;
    for (int i = n - 3; i >= 0; i--) {
        for (int j = i + 2; j < n; j++) {
            if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) dp[i][j] = 1;
        }
    }

    int maxlen = 0;
    int left;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (dp[i][j] == 1 && j - i + 1 > maxlen) {
                maxlen = j - i + 1;
                left = i;
            }
        }
    }

    return s.substr(left, maxlen);
}



/**
 * @方法: 普通循环
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
string longestPalindrome(string s) {
    int from;
    int to;
    int maxlen = -1;
    for (int i = 0; i < s.length(); i++) {
        // odd
        int left = i - 1;
        int right = i + 1;
        while (left >= 0 && right < s.length()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            } else {
                break;
            }
        }
        if (right - left - 1 > maxlen) {
            maxlen = right - left - 1;
            from = left + 1;
            to = right - 1;
        }

        // even
        left = i;
        right = i + 1;
        while (left >= 0 && right < s.length()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            } else {
                break;
            }
        }
        if (right - left - 1 > maxlen) {
            maxlen = right - left - 1;
            from = left + 1;
            to = right - 1;
        }
    }
    return s.substr(from, to - from + 1);
}

int main() {
    string s = "cbbd";
    string ans = longestPalindrome(s);
    cout << ans << endl;
    return 0;
}